package leetcode_200;

import java.util.LinkedList;

/**
 *@author 周杨
 *SurroundedRegions_130 黑白棋游戏问题
 *describe:用fill填充法解决 开始先判断有哪些点可以通过边界走到  走的策略采取广度优先遍历  能走到的先用#标记 到时候再遍历 若不是#的再反转成O AC 66%
 *2018年5月29日 上午10:26:45
 */
public class SurroundedRegions_130 {
	char[][] board;
	int row;
	int col;
	public static void main(String[] args) {
		SurroundedRegions_130 test=new SurroundedRegions_130();
		char board[][]=new char[][] {{'X','X','X','X'},{'X','O','O','X'},
			{'X','X','O','X'},
			{'X','O','X','X'}};
			test.solve(board);

	}
	
	public void solve(char[][] board) {  
	    if(board==null || board.length<=1 || board[0].length<=1)  
	        return;  
	    for(int i=0;i<board[0].length;i++)  //行填充 第一行  和最后一行
	    {  
	        fill(board,0,i);  
	        fill(board,board.length-1,i);  
	    }  
	    for(int i=0;i<board.length;i++)  //列填充 第一列 和最后一列  相当于把边填满先
	    {  
	        fill(board,i,0);  
	        fill(board,i,board[0].length-1);  
	    }  
	    for(int i=0;i<board.length;i++)  
	    {  
	        for(int j=0;j<board[0].length;j++)  
	        {  
	            if(board[i][j]=='O')  
	                board[i][j]='X';  
	            else if(board[i][j]=='#')  
	                board[i][j]='O';                  
	        }  
	    }  
	}  
	private void fill(char[][] board, int i, int j)  
	{  
	    if(board[i][j]!='O')  //X和#不用填充
	        return;  
	    board[i][j] = '#';  
	    LinkedList<Integer> queue = new LinkedList<Integer>();  
	    int code = i*board[0].length+j; //唯一编码 列数乘以行+列 
	    queue.offer(code);  
	    while(!queue.isEmpty())  
	    {  
	        code = queue.poll();  
	        int row = code/board[0].length;  
	        int col = code%board[0].length;  
	        if(row>0 && board[row-1][col]=='O')  //上
	        {  
	            queue.offer((row-1)*board[0].length+col);  
	            board[row-1][col]='#';  
	        }  
	        if(row<board.length-1 && board[row+1][col]=='O')  //下
	        {  
	            queue.offer((row+1)*board[0].length+col);  
	            board[row+1][col]='#';  
	        }  
	        if(col>0 && board[row][col-1]=='O')  //左
	        {  
	            queue.offer(row*board[0].length+col-1);  
	            board[row][col-1]='#';  
	        }  
	        if(col<board[0].length-1 && board[row][col+1]=='O')  //右
	        {  
	            queue.offer(row*board[0].length+col+1);  
	            board[row][col+1]='#';  
	        }              
	    }  
	}  
}
